#ifndef BOOTSTRAPPING_POLYARITH_H
#define BOOTSTRAPPING_POLYARITH_H
#include <vector>
#include <cassert>
#include <ostream>
#include "../utils.h"
#include "../prng.h"
#include "../encryptor.h"
#include "../utils.h"
#include "../context.h"
#include "../ring_scaling.h"
#include "../ring.h"
#include "../ring_poly.h"
#include "../operand.h"
#include "../ring_sampler.h"
#include "../keygen.h"
#include "../ring_basis_extension.h"
#include "../modular_reduction.h"
#include "../encryptor.h"
#include "../decryptor.h"
#include "../evaluator.h"

/*
 * 在明文空间中稍微快速的多项式计算
 */

typedef std::vector<uint64_t> poly;

struct PolyModulus {
    poly xPowerN;
    size_t n;
};


void PolyNormalize(poly &p);
void PolyAdd(poly &lhs, const poly &rhs, const uint64_t &mod, uint64_t scale = 1, size_t powerXScale = 0);
poly PolyExponentiateMod(const poly &basis, size_t exp, const uint64_t &mod, const PolyModulus &pmod);
void PolyScale(poly &p, uint64_t scale, const uint64_t &mod);
poly PolyMulMod(const poly &lhs, const poly &rhs, const uint64_t &mod, const PolyModulus &pmod);
void PolyReduceMod(poly &lhs, const uint64_t &mod, const PolyModulus &pmod);
void PolySubMul(poly &dst, const poly &lhs, const poly &rhs, const uint64_t &mod);
void PolyAddMul(poly &dst, const poly &lhs, const poly &rhs, const uint64_t &mod);
std::tuple<int64_t, int64_t> Eea(uint64_t a, uint64_t b);
uint64_t PolyEval(const poly &p, uint64_t x, const uint64_t &mod);
poly PolyDivRem(poly &lhs, const poly &rhs, const uint64_t &mod);
std::tuple<poly, poly, poly> PolyEea(poly lhs, poly rhs, const uint64_t &mod);
uint64_t InvMod_(uint64_t x, const uint64_t &mod);
bool IsZero(const poly &x);
bool IsIrreducible(const poly &x, const uint64_t &primeModulus);
void TestIsIrreducible();
/*
 * @brief 高效计算整数的幂
 * 它通过遍历 `exp` 的二进制位，将幂的计算分解为更小的步骤，从而提高计算效率。
 * @param base 底数。
 * @param exp 指数。
 *
 * @return 返回 `base` 的 `exp` 次幂。
 */
inline uint64_t IPow(uint64_t base, uint64_t exp)
{
    uint64_t result = 1;
    for (int64_t i = std::numeric_limits<unsigned long>::digits - 1; i >= 0; --i) {
        if (((exp >> i) & 1) == 1) {
            result = result * result * base;
        } else {
            result = result * result;
        }
    }
    return result;
}
inline void PolySub(poly &lhs, const poly &rhs, const uint64_t &mod, uint64_t scale = 1, size_t powerXScale = 0)
{
    PolyAdd(lhs, rhs, mod, NegateUintMod(scale, mod), powerXScale);
}
#endif